package prac8;

import java.util.Stack;

import javax.tools.JavaCompiler;

/**
 * binary search list tree data type implemented with linked nodes.
 * 
 * @author          Menghong Li
 * 					Brendan Peterson 
 * @modified        Menghong Li & Brendan Peterson(September 2011)
 * @param           <K> data type for the key for each node in this tree
 * @param           <T> data type for the elements in the data for each node in this tree
 * @since           Sept 2011
 * @input           none
 * @output          only for regression t
 * sting
 * @errorHandling   none
 * @knownBugs       none
 */


/*
 * Invariants:
 *   (1) the tree is binary: all nodes have at most two children
 *   (2) for every node n, they key at n is greater than the key of any left
 *       descendant, and smaller than the key of any right descendant
 *   (3) Corollary: no key appears twice in the tree
 */
public class BinarySearchListTree<K extends Comparable<K>, T extends Comparable<T>> {
	/** marks the root of the tree, null if empty */
	protected Node root;
	
    /**
     * Implements each node. 
     * Defined as protected since only descendant classes need to access it.
     * 
     * @author    Menghong Li
     * 			  Brendan Peterson
     * @modified  Menghong Li & Brendan Peterson(September 2011)
     */
	protected class Node {
		protected SortedLinkedList<T> item;
		protected K key;
		protected Node left;
		protected Node right;
		
        /**
		 * @return the left
		 */
		protected Node getLeft() {
			return left;
		}

		/**
		 * @param left the left to set
		 */
		protected void setLeft(Node left) {
			this.left = left;
		}

		/**
		 * @return the right
		 */
		protected Node getRight() {
			return right;
		}

		/**
		 * @param right the right to set
		 */
		protected void setRight(Node right) {
			this.right = right;
		}

		/**
		 * @return the item
		 */
		protected SortedLinkedList<T> getItem() {
			return item;
		}

		/**
		 * @return the key
		 */
		protected K getKey() {
			return key;
		}

		/**
         * Creates a new leaf node of the tree with the appropriate data.
         * 
         * @param       key to use for this node
         * @param       newItem to store in the sortedLinkedList associated with this node
         * @post        a leaf node object is created with key data key
         *              and item newItem
         * @complexity  best and worse case: O(1) 
         */
		protected Node(K key, T newItem) {
			item = new SortedLinkedList<T>();
			item.add(newItem);
			this.key = key;
			this.left = null; 
			this.right = null;
		}

        /**
         * Creates a new node of the tree with the appropriate data and pointing
         * to the given left and right children nodes.
         * 
         * @param       key to use for this node
         * @param       newItem to store in the sortedLinkedList associated with this node
         * @param       l node to store in the left branch
         * @param       r node to store in the right branch
         * @post        a node object is created with key data newKey, item
         *              newItem, and left and right nodes pointing to l and r
         * @complexity  best and worse case: O(1)
         */
		protected Node(K key, T newItem, Node left, Node right) {
			item = new SortedLinkedList<T>();
			item.add(newItem); 
			this.key = key;
			this.left = left;       
			this.right = right;
		} 
	}
		
	/**
     * Implements a tree iterator.
     * 
     * @author    Menghong Li
     * @modified  Menghong Li & Brendan Peterson(September 2011)
     */
    

	protected class MyIterator implements TreeIterator<K, SortedLinkedList<T>>{

		private Stack<Node> stack = new Stack<Node>();
		
		/**
		 * Pushes the most left node in each level to stack (from top to bottom)
		 * 
		 * @post 		all most left nodes in each level are added to stack
		 * @param 		x
		 * @complexity 	Best case and worst case O(D * P) 
		 * 				where 	D is the depth of the tree 
		 * 						P is the complexity of {@link java.util.Stack#push()}
		 */
		private void pushLeft(Node x)
		{
			while (x != null){  
				stack.push(x); 
				x = x.getLeft();
			}
		}
		/**
		 * Constructor for MyIterator
		 * 
		 * @post 		Most left node of each level of BinarySerachListTree has been pushed into the stack
		 * @complexity 	Best case and worst case O(P) 
		 * 				where P is the complexity of {@link BinarySearchListTree.MyItertor#pushLeft(Node)}
		 */
		public MyIterator() {
			pushLeft(root); 
		}
		
		/**
		 * Check if MyIterator has next node
		 * 
		 * @return True if stack is not empty, False otherwise.
		 * @complexity O({@link java.util.Stack#isEmpty()})
		 */
		public boolean hasNext(){  
			return (!stack.isEmpty()); 
		}
		
		/**
		 * Returns the next pair of BinarySearchListTree and removes from stack
		 * 
		 * @return 		next pair of key and SortedLinkedList of item
		 * @complexity 	Best case and Worst case of O(E + P + L) 
		 * 				where 	E is the complexity of {@link java.util.Stack#isEmpty()}
		 * 						P is the complexity of {@link java.util.Stack#pop()} 
		 * 						L is the complexity of {@link BinarySearchListTree.MyItertor#pushLeft(Node)} 
		 */
		public Pair<K, SortedLinkedList<T>> next()
		{
			Node current = stack.pop();
			pushLeft(current.getRight());
			return  new Pair<K, SortedLinkedList<T>>(current.getKey(), current.getItem());
		}
		
		/**
		 * Returns next pair of BinarySearchListTree
		 * 
		 * @return 		next pair of key and SortedLinkedList of item
		 * @complexity 	Best case and Worst case of O(E + P) 
		 * 				where	E is the complexity of {@link java.util.Stack#isEmpty()}
								P is the complexity of {@link java.util.Stack#peek()}
		 */
		public  Pair<K, SortedLinkedList<T>>  peek() {
			Node current = stack.peek();
			if(hasNext()){
				return new Pair<K, SortedLinkedList<T>>(current.getKey(), current.getItem());
			}
			
			throw new NoSuchElementException("at peek()");
		}

		/**
		 * Resets the TreeIterator
		 * 
		 * @complexity 	Best case and worst case of O(P + C) 
		 * 				where 	C is the complexity of {@link java.util.Stack#clear()}
								P is the complexity of {@link #pushLeft(Node)}
		 */
		public void reset() {
			stack.clear();
			pushLeft(root);
		}
		
	}
	
    /**
     * Creates a new iterator for the Binary Search List Tree.
     * 
     * @return      new abstract list iterator
     * @see         TreeIterator#TreeIterator()
     */
	public TreeIterator<K, SortedLinkedList<T>> iterator(){
		return new MyIterator();
	}
	
	/**
	 * Construct method to initialise the BST
	 * 
	 * @complexity	Best and worst case O(1)
	 */
	public BinarySearchListTree() {
		root = null;
	}
	
	/**
	 * Inserts a new node (key/item) into the tree
	 * 
	 * @param       key		the key to use for the new node
	 * @param       item	the item to store inside the new node
	 * @post        the tree contains all previous elements in the same
	 *              positions, plus the new one in a leaf node. Of course,
	 *              the tree is still a binary search tree
	 * @complexity	Best case: O(1)
	 * 				worst case: O(P) where P is the complexity of {@link BinarySearchListTree#internalInsert(Node, Comparable, Comparable)()}
	 */
	public void insert(K key, T item){
	    if (root == null) {
	        root = new Node(key, item);     
	    }else{
	        internalInsert(root, key, item);
	    }
	}
	
	/**
	 * Recursively inserts a new node (key/item) into the tree
	 * 
	 * @param 		Node	 the current node in the BinarySearchListTree	
	 * @param 		key		 the key to use for the new node
	 * @param       item  	 the item to store inside the new node
	 * @post        the tree contains all previous elements in the same
	 *              positions, plus the new one in a leaf node. Of course,
	 *              the tree is still a binary search tree
	 *
	 * @complexity 	best case  O(F) where the key is the root node 
	 * 				worst case O(F + A + C) * O(logN) 
					where	N is the size of BinarySearchTree
							F is the complexity of {@link SortedLinkedList#find(Object)}
							A is the complexity of {@link SortedLinkedList#add(Comparable)}
//							C is the complexity of {@link Java.lang.Comparable#compareTo}
	 */
	private void internalInsert(Node node, K key, T newItem){
	    // Not the same value twice
	    if (key.compareTo(node.getKey()) == 0) {
	        if(!node.getItem().find(newItem)){
	        	node.getItem().add(newItem);
	        }
	    } else if (key.compareTo(node.getKey()) < 0 ) {
	        if (node.getLeft() == null) {
	            node.setLeft(new Node(key, newItem, null, null));
	        }else{
	            internalInsert(node.getLeft(), key, newItem);
	        }
	    }else{
	        if (node.getRight() == null) {
	            node.setRight(new Node(key, newItem, null, null));
	        }else{
	            internalInsert(node.getRight(), key, newItem);
	        } 
	    }
	}

	/**
	 * Used to print all keys and items following inOrder of the nodes
	 * 
	 * @post        the key and item of every node is printed in inOrder
	 * @complexity  Best and worst case O(K) 
	 * 				where	 K is the complexity of {@link BinarySearchListTree#printInOrderAux(Node)}
	 */
	public void printInOrder(){
		printInOrderAux( root );
	}
	
	/**
	 * Recursively print all keys and items following inOrder of the nodes
	 * 
	 * @post        the key and item of every node is printed in inOrder
	 * @complexity  Best and worst case O(N*(P*N1) 
	 * 				where	N is the number of elements in the tree
	 * 						P is the complexity of {@link java.io.PrintStream#print(String)}
							N1 is the number of items in the SortedLinkedList
	 */
	private void printInOrderAux(Node currentNode){
		if (currentNode != null) { //not a base case
			printInOrderAux(currentNode.getLeft());
			System.out.println("Key:" + currentNode.getKey());
			Iterator<T> i = currentNode.getItem().iterator();
			while(i.hasNext()){
				System.out.print(i.peek() + "\t");
				i.next();
			}
			System.out.println();
			printInOrderAux(currentNode.getRight());
			}
	}
	
	/**
	 * Searches if a key and element are in the BinarySearchListTree
	 * 
	 * @param key	 		the key to search for
	 * @param thisElement 	the element in the SortedLinkedList to search for
	 * @complexity 			Best case O(1) BinarySearchTree is empty 
	 * 						worst case O(P)
	 * 						where	P is the complexity of {@link BinarySearchListTree#find(Node, Comparable, Comparable)}
	 * @return 				true if key and item is in tree, false otherwise
	 */
	public boolean find(K key,T thisElement){
		if (root == null) {
			return false;
		} else {
			return findAux(root, key, thisElement);
		}
	}
	
	/**
	 * Recursively searches the BinarySearchListTree for a key and element 
	 * 
	 * @param currentNode	the current node in the BinarySearchListTree
	 * @param key			the key to search for
	 * @param thisItem		the element in the SortedLinkedList to search for
	 * @complexity 			Best case O(C + F) when the element is at the root
							worst case O((log(N) * C) + F) 
							where	F is the complexity of {@link SortedLinkedList#find(Object)}
									C is the complexity of {@link Java.lang.Comparable#compareTo} 
									N is the size of BinarySearchTree
	 * @return true if key and item is in tree, false otherwise
	 */
	private boolean findAux(Node currentNode, K key, T thisElement){
		if(currentNode == null){
			return false;
		} else if(currentNode.getKey().compareTo(key) > 0){
			return findAux(currentNode.getLeft(), key, thisElement);
		} else if(currentNode.getKey().compareTo(key) == 0){
			return currentNode.getItem().find(thisElement);
		} else {
			return findAux(currentNode.getRight(), key, thisElement);
		}
		
	}
	
	/**
	 * 	searches BinarySearchListTree for anagrams of a word and prints them
	 *  
	 * @param key	the key node in BinarySearchListTree
	 * @param thisElement
	 * @complexity	O(P) where P is the complexity of {@link BinarySearchListTree#printAnagramsAux(Node, Comparable, Comparable)}
	 * 
	 */
	public void printAnagrams(K key, T thisElement){
		printAnagramsAux(root, key, thisElement);
	}
	
	/**
	 * Recursively searches BinarySearchListTree for anagrams of a word
	 * 
	 * @param current	the current node to be searched in the BinarySerachListTree
	 * @param theKey	the key node in BinarySearchListTree
	 * @param theItem	the word to find anagrams of
	 * @complexity 		best case O(P * N) where the key is the root node
	 * 					worst case O(D * C * (P * N)) 
	 * 					where	D is the depth of BinarySearchListTree
								P is the complexity of {@link java.io.PrintStream#print(String)}
								N is the number of items in the SortedLinkedList
								C is the complexity of (@link Java.lang.Comparable#compareTo)
	 */
	private void printAnagramsAux(Node currentNode, K key, T thisElement){
		if(currentNode == null){
			System.out.println("No anagram found.");
		} else if(currentNode.getKey().compareTo(key) > 0){
			printAnagramsAux(currentNode.getLeft(), key, thisElement);
		} else if(currentNode.getKey().compareTo(key) == 0){
			if(currentNode.getItem().length != 1){
				System.out.println("Key: " + currentNode.getKey());
				Iterator<T> i = currentNode.getItem().iterator();
				while(i.hasNext()){
					if(i.peek().compareTo(thisElement) != 0){
						System.out.print(i.peek() + "\t");
					}
					i.next();
				}
				System.out.println();
			} else {
				System.out.println("No anagram found.");
			}
		} else {
			printAnagramsAux(currentNode.getRight(), key, thisElement);
		}
	}
	
	/**
	 * test method for PrintInOrder
	 * 
	 * @complexity O(1)
	 */
	public static void testPrintInOrder(){
		// test case 1 : the parent of the last node in the tree doesn't has left child.
		System.out.println("test case 1 : the parent of the last node in the tree doesn't has left child.");
		BinarySearchListTree<String, String> BST = new BinarySearchListTree<String, String>();
		BST.insert("43", "1");
		BST.insert("31", "1");
		BST.insert("31", "1");
		BST.insert("20", "1");
		BST.insert("28", "1");
		BST.insert("40", "1");
		BST.insert("33", "1");
		BST.insert("64", "1");
		BST.insert("56", "1");
		BST.insert("47", "1");
		BST.insert("59", "1");
		BST.insert("89", "1");
		
		BST.printInOrder();
		System.out.println(BST.find("40", "2"));
		
		//test case 2: the parent of the last node in the tree doesn't has right child.
		System.out.println("test case 2: the parent of the last node in the tree doesn't has right child.");
		BinarySearchListTree<String, String> BST2 = new BinarySearchListTree<String, String>();
		BST2.insert("43", "1");
		BST2.insert("31", "1");
		BST2.insert("20", "1");
//		BST2.insert("28", "1");
		BST2.insert("40", "1");
		BST2.insert("33", "1");
		BST2.insert("64", "1");
		BST2.insert("56", "1");
		BST2.insert("47", "1");
		BST2.insert("59", "1");
		BST2.insert("89", "1");
		
		BST2.printInOrder();
		
		//test case 3: complete tree
		System.out.println("test case 3: complete tree");
		BinarySearchListTree<String, String> BST3 = new BinarySearchListTree<String, String>();
		BST3.insert("43", "1");
		BST3.insert("31", "1");
		BST3.insert("20", "1");
//		BST3.insert("28", "1");
		BST3.insert("40", "1");
//		BST3.insert("33", "1");
		BST3.insert("64", "1");
		BST3.insert("56", "1");
//		BST3.insert("47", "1");
//		BST3.insert("59", "1");
		BST3.insert("89", "1");
		
		BST3.printInOrder();
	}
	
	/**
	 * test method for Iterator()
	 * 
	 * @complexity O(D) where	D is the complexity of depth of the tree
	 */
	public void testIterator(){
		TreeIterator<K, SortedLinkedList<T>> iterator = this.iterator();
		while (iterator.hasNext()) {
			Pair<K, SortedLinkedList<T>> node = iterator.next();
			System.out.print( node.getFirst() + " ");
		}
	}
	
	/**
	 * test method for find()
	 * 
	 * @complexity O(1)
	 */
	public static void testFind(){
		BinarySearchListTree<String, String> BST = new BinarySearchListTree<String, String>();
		BST.insert("43", "1");
		BST.insert("31", "1");
		BST.insert("20", "1");
		BST.insert("28", "1");
		BST.insert("40", "1");
		BST.insert("33", "1");
		BST.insert("64", "1");
		BST.insert("56", "1");
		BST.insert("47", "1");
		BST.insert("59", "1");
		BST.insert("89", "1");
		
		// test case 1
		System.out.println(BST.find("40", "1"));
		
		// test case 2
		System.out.println(BST.find("40", "2"));
		
		// test case 3
		System.out.println(BST.find("32", "1"));
	}
	
	/**
	 * test method for insert()
	 * 
	 * @complexity O(1)
	 */
	public static void testInsert(){
		BinarySearchListTree<String, String> tree = new BinarySearchListTree<String, String>();
		tree.insert("abd", "bad");
		tree.insert("abd", "dab");
		tree.insert("abd", "dab");
		tree.insert("acr", "car");
		tree.printInOrder();
		System.out.println();
	}
	
	public static void main(String args[]){
//		testPrintInOrder();
//		testFind();
		testInsert();
		
		
		
	}
}
